The problem can be found at the following link: Question Link
To solve this problem, I utilize a dynamic programming approach to track the maximum profit achievable by making transactions at each day. Specifically:
- I iterate through the prices array once to compute the maximum profit that can be obtained by making one transaction up to that day and store it in the 'left' array.
- Then, I iterate through the prices array in reverse to compute the maximum profit that can be obtained by making two transactions. During this iteration, I combine the profit obtained from the first transaction (stored in 'left' array) with the profit obtained by selling on the current day.
- Time Complexity: The time complexity of this approach is
O(n)
, where n is the number of elements in theprice
vector. - Auxiliary Space Complexity: The auxiliary space complexity is
O(n)
, where n is the number of elements in the 'price' vector.
class Solution {
public:
int maxProfit(vector<int>& price) {
int n = price.size();
vector<int> left(n, 0);
int nin = price[0];
int out = 0;
for (int i = 1; i < n; ++i) {
nin = min(nin, price[i]);
left[i] = max(left[i - 1], price[i] - nin);
out = max(out, left[i]);
}
int nax = price[n - 1];
for (int i = n - 2; i > 0; --i) {
nax = max(nax, price[i]);
out = max(out, left[i - 1] + nax - price[i]);
}
return out;
}
};
For discussions, questions, or doubts related to this solution, please visit our discussion section. We welcome your input and aim to foster a collaborative learning environment.
If you find this solution helpful, consider supporting us by giving a ⭐ star
to the getlost01/gfg-potd repository.